1. Field of Invention
This invention relates in general to error correcting systems employing cyclic error correcting codes and, in particular, to an improved method and apparatus for processing syndrome bytes in a multibyte error correcting system.
2. Cross-Referenced Application
Application Ser. No. 454,393, filed concurrently herewith, entitled "On-the-Fly Multibyte Error Correcting System", A. M. Patel, assigned to the assignee of the present invention, discloses a on-the-fly multibyte error correcting system.
3. Description of the Prior Art
The use of cyclic error correcting codes in connection with the storage of data in magnetic storage devices is well established in the prior art and is generally recognized as a very efficient and cost effective addition to the storage system.
Generally, the error correcting process involves the processing of syndrome bytes to determine the location and pattern of each error that is detected. Syndrome bytes result from the exclusive-ORing of ECC write check characters that are generated as data is being written on the storage medium and ECC read check characters that are generated when the data is transferred from or read from storage. The number of ECC check characters employed depends on the desired power of the code and the number of data bytes to be checked or protected. As an example, in many present day ECC systems which are used in connection with the storage of 8-bit bytes in a magnetic storage device, two check bytes are used for each error to be checked in a codeword having a length of 255 byte positions. Thus, for example, six check bytes are required to detect up to three errors in a block of data having 249 data bytes and six check bytes. Thus, six distinctive syndrome bytes are generated in such a system. If there are no errors in the data word comprising the 255 bytes read from storage, then all six syndrome bytes each contain an all zero pattern. Under such a condition, no syndrome processing is required and the data word may be sent to the central processing unit. However, if one or more of the syndrome bytes is non-zero, then syndrome processing involves the process of identifying the location of the bytes in error and further identifying the error pattern for each error location.
The prior art has disclosed in various publications and patents the underlying mathematical concepts and operations which are involved in normal syndrome processing operations. These operations and mathematical explanations generally involve first identifying the location of the errors by use of what has been referred to by Peterson as the "error locator polynomial". The overall objective of the mathematics involved employing the error locator polynomial is to define the locations of the bytes in error by using only the syndrome bytes that are generated in the system.
The prior art has employed the error locator polynomial as the start of the mathematical analysis to express error locations in terms of syndromes so that binary logic may be employed to decode the syndrome bytes into first identifying the locations in error so that subsequent hardware can identify the error patterns in each location. Two problems have existed with the error locator portion of prior art syndrome processing decoders for multi-error correcting systems.
The first problem is that separate sets of logic were required for each of the multi-error conditions. For example, if the system was designed to correct up to three errors, three separate and independent sets of logic were required to identify the error location. That is, the logic required to identify the error locations when there were three errors could not be used to identify the locations if there were less than three errors, i.e., two or a single error. Likewise, the logic designed to identify the error locations if two errors were present could not identify the error location if only one error existed in the codeword. The cost of such prior art decoders was, therefore, quite high.
The second problem with prior art syndrome processing decoders for multibyte error correcting systems is that a division step was required in the mathematical processing of the syndrome bytes to arrive at error locations. It is well recognized that a division operation in higher order binary fields is costly, both in time and hardware implementation.
The present invention provides a decoder for syndrome processing in a multibyte error correcting system which is capable of identifying each error location in a manner which avoids using a division operation and which employs a subset of the hardware used for identifying the maximum number of error locations in the system where the number of errors is less than maximum.